#Some tools
def Z(a):
a2 = a.zero_complete2()
a2.zero_completeOP()
return a2.emonde().minimise()
def Pref(a):
r = a.emonde()
r.set_final_states(r.states())
return r
#Automaton whose language is a given word
def AutWord (w, A=None):
if A is None:
A = set(w)
if len(w) == 0:
return FastAutomaton([(0, 1, l) for l in A],i=0,final_states=[0])
else:
return FastAutomaton([(i,i+1,l) for i,l in enumerate(w)]+[(len(w)+1, len(w)+1, l) for l in A],i=0,final_states=[len(w)])
#Automaton whose language is a given set of words
def MakeAut(l):
start = False
for w in l:
if not start:
start=True
u = AutWord(w)
else:
u = u.union(AutWord(w))
return u
#project a on b
def Proj(a,b, t=0):
arel = m.relations_automaton4(t=t, couples=True, A=m.C, B=m.C)
ai = arel.intersection(Z(b).product(Z(a)))
d = {}
for i in m.C:
for j in m.C:
d[(i,j)] = i
return Z(ai.proj(d))
#project a on b with lengths preserved
def Proj2(a,b, t=0):
arel = m.relations_automaton4(t=t, couples=True, A=m.C, B=m.C)
ai = arel.intersection(b.product(a))
d = {}
for i in m.C:
for j in m.C:
d[(i,j)] = i
return ai.proj(d)
#test if b-sets are equal
def eqQ(a,b,t=0):
return Proj(a,b,t=t).equals_langages(Z(b)) and Proj(b,a,t=-t).equals_langages(Z(a))
#S^{0,\Sigma}
def S0S (L):
L2 = L.copy()
A = L2.Alphabet()
for e in L2.states():
for i in range(len(A)):
if L2.succ(e, i) != -1:
if A[i][0] != 0:
L2.set_succ(e, i, -1) #suppress edges not of the form (0,*)
#return L2
cc = L2.strongly_connected_components(no_trivials=True)
print len(cc)
F = [e for c in cc if len([e for e in c if not L.is_final(e)]) == 0 for e in c]
print F
L2.set_final_states(F)
F = list(set(L2.coaccessible_states()).intersection(set(L.final_states())))
print F
L2 = L.copy()
L2.set_final_states(F)
return L2.emonde().minimise()
def S(L):
cc = L.strongly_connected_components(no_trivials=True)
print len(cc)
F = [e for c in cc if len([e for e in c if not L.is_final(e)]) == 0 for e in c]
print F
L2 = L.copy()
L2.set_final_states(F)
F = list(set(L2.coaccessible_states()).intersection(set(L.final_states())))
L2.set_final_states(F)
return L2.emonde().minimise()
#Save a FastAutomaton
def Save(a):
E = []
A = a.Alphabet()
for e in a.states():
for l in range(len(A)):
if a.succ(e, l) != -1:
E.append((e, a.succ(e,l), A[l]))
print "FastAutomaton(%s, i=%s, final_states=%s)"%(E, a.initial_state(), a.final_states())
|
|
#substitution of the minimal Pisot number
s = WordMorphism('1->2,2->3,3->12')
print "Substitution of the minimal Pisot number"
show(s)
#draw the Rauzy fractal
m = s.rauzy_fractal_beta_adic_monoid()
print m
s = FastAutomaton(m.tss)
m.plot2(tss=s)
Substitution of the minimal Pisot number Monoid of b-adic expansion with b root of x^3 - x - 1 and numerals set
{0, 1} with subshift of 3 states
Substitution of the minimal Pisot number Monoid of b-adic expansion with b root of x^3 - x - 1 and numerals set {0, 1} with subshift of 3 states
|
#zoom on the Rauzy fractal
m.draw_zoom(tss=s)
m.plot2(tss=s, ajust=False)
.png)
|
#Hokkaido substitution
h = WordMorphism('1->12,2->3,3->4,4->5,5->1')
print "Hokkaido Substitution"
show(h)
m = h.rauzy_fractal_beta_adic_monoid()
h = FastAutomaton(m.tss)
print h
h.plot()
m.plot2(tss=h, coeff=8)
Hokkaido Substitution FastAutomaton with 5 states and an alphabet of 2 letters Hokkaido Substitution FastAutomaton with 5 states and an alphabet of 2 letters .png) 
|
############################################################
# Relations language and countable union of Hokkaido tiles #
############################################################
|
|
#calcul de Lrel
arel = m.relations_automaton4(t=0, couples=True, A=m.C, B=m.C)
arel
FastAutomaton with 179 states and an alphabet of 4 letters FastAutomaton with 179 states and an alphabet of 4 letters |
#check that Q_{0^3L_s} is included in Q_{L_h}
Proj(h, s.unshift(0,3)).equals_langages(Z(s.unshift(0,3)))
True True |
#project 0^3L_s on L_h
a = Proj(s.unshift(0,3), h)
a
FastAutomaton with 197 states and an alphabet of 2 letters FastAutomaton with 197 states and an alphabet of 2 letters |
m.plot2(tss=a, coeff=6)
.png)
|
A = a.copy()
cc = a.strongly_connected_components()
for c in cc:
if len(c) == 5:
#test if every state of c is final
ok = True
for e in c:
if not a.is_final(e):
ok = False
break
if ok:
#look for the unic state of c with two transistion leaving from it
for e in c:
if a.succ(e,0) != -1 and a.succ(e,1) != -1:
A.set_succ(e,0,-1) #remove these transitions
A.set_succ(e,1,-1)
A.set_final_states([e]) #take e as the only final state
break
#now A recognize the language A
A = A.emonde().minimise()
A
FastAutomaton with 197 states and an alphabet of 2 letters FastAutomaton with 197 states and an alphabet of 2 letters |
len(A.final_states())
1 1 |
a.equals_langages(Z(a))
True True |
#M is the complementary of Z(A.h) in a
M = a.intersection(Z(A.concat(h)).complementary())
M
FastAutomaton with 191 states and an alphabet of 2 letters FastAutomaton with 191 states and an alphabet of 2 letters |
M.equals_langages(Z(M))
True True |
A.concat(h).equals_langages(Z(A.concat(h)))
False False |
#plot the countable union of Hokkaido
m.plot2(tss=A.concat(h))
.png)
|
#plot M and check that is has dimension < 2
m.plot2(tss=M, coeff=6)
print "dimension %s"%m.critical_exponent_free(M)
log(y)/log(|b|) where y is the max root of x^13 - x^12 - x^10 + x^9 - 2*x^4 + x^3 - 1 dimension 1.94643460326528 log(y)/log(|b|) where y is the max root of x^13 - x^12 - x^10 + x^9 - 2*x^4 + x^3 - 1 dimension 1.94643460326528 .png)
|
#########################################################
# Extended relations automaton and three type of shapes #
#########################################################
|
|
#calcul de Lrelinf
arelinf = m.relations_automaton4(t=0, ext=True, couples=True, A=m.C, B=m.C)
print arelinf
arelinf.equals_langages(arel)
FastAutomaton with 179 states and an alphabet of 4 letters False FastAutomaton with 179 states and an alphabet of 4 letters False |
#compute B such that Q_B = Q_h \ adh(Q_{0^3 s})
L = S0S(Z(h).product(Pref(Z(s.unshift(0,3)))).intersection(arelinf)).proji(0)
B = Z(h).intersection(L.complementary())
m.plot2(tss=B)
3 [66, 67, 73, 78, 80, 26, 33, 34, 41] [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 33, 34, 35, 39, 40, 41, 43, 44, 47, 48, 49, 53, 54, 55, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91] 3 [66, 67, 73, 78, 80, 26, 33, 34, 41] [18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 33, 34, 35, 39, 40, 41, 43, 44, 47, 48, 49, 53, 54, 55, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91] .png)
|
#check that Q_M is included in the adherence of Q_B
ai = Z(M).product(Pref(Z(B))).emonde().minimise().intersection(arelinf)
print ai
#apply S^{0,\Sigma}
ai = S0S(ai)
print ai
M2 = ai.proji(0)
print M2
print M2.included(M)
print M.included(M2)
FastAutomaton with 3240 states and an alphabet of 4 letters 11 [30, 32, 53, 86, 90, 91, 92, 96, 97, 98, 99, 100, 194, 197, 209, 31, 58, 89, 126, 127, 128, 129, 136, 146, 147, 162, 180, 188, 189, 205, 38, 74, 87, 93, 94, 95, 154, 158, 159, 172, 176, 179, 195, 196, 210, 39, 40, 41, 75, 76, 77, 78, 80, 81, 88, 108, 109, 153, 156, 199, 42, 43, 44, 45, 46, 47, 56, 57, 107, 110, 111, 112, 113, 135, 200, 52, 55, 106, 114, 115, 116, 117, 137, 138, 141, 148, 155, 157, 160, 161, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 122, 124, 130, 198, 123, 125, 131, 139, 140, 204] [30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210] FastAutomaton with 191 states and an alphabet of 4 letters FastAutomaton with 191 states and an alphabet of 2 letters True True FastAutomaton with 3240 states and an alphabet of 4 letters 11 [30, 32, 53, 86, 90, 91, 92, 96, 97, 98, 99, 100, 194, 197, 209, 31, 58, 89, 126, 127, 128, 129, 136, 146, 147, 162, 180, 188, 189, 205, 38, 74, 87, 93, 94, 95, 154, 158, 159, 172, 176, 179, 195, 196, 210, 39, 40, 41, 75, 76, 77, 78, 80, 81, 88, 108, 109, 153, 156, 199, 42, 43, 44, 45, 46, 47, 56, 57, 107, 110, 111, 112, 113, 135, 200, 52, 55, 106, 114, 115, 116, 117, 137, 138, 141, 148, 155, 157, 160, 161, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 70, 122, 124, 130, 198, 123, 125, 131, 139, 140, 204] [30, 31, 32, 33, 34, 35, 36, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210] FastAutomaton with 191 states and an alphabet of 4 letters FastAutomaton with 191 states and an alphabet of 2 letters True True |
M.equals_langages(M2)
True True |
a_t1 = FastAutomaton([(0,1,0),(1,2,0),(2,3,0),(3,4,0),(4,0,0),(0,5,1),(5,6,0),(6,7,0),(7,8,0),(8,9,0),(9,9,0),(9,5,1)], i=0, final_states=[5,6,7,8,9])
a_t1.plot()
a_t2 = Z(FastAutomaton([(10, 8, 0),(8,17,0),(17,6,0),(10, 13, 1), (6,5,0),(5,9,0),(9,16,0),(6,13,1),(16,13,1),(16,27,0),(27,24,0),(24,25,0),(13,12,0),(12,11,0),(11,15,0),(15,18,0),(18,7,0),(7,14,0),(14,19,0),(19,4,0),(4,18,0),(4,22,1),(25,1,0),(1,26,0),(26,23,1),(24,23,1),(23,2,0),(2,21,0),(21,20,0),(20,3,0),(3,3,0),(3,22,1),(22,0,0),(0,21,0),(9,22,1)], i=10, final_states=[0,21,20,3,22]))
a_t2.plot()
a_t3 = Z(FastAutomaton([(13,1,0),(1,23,0),(23,22,0),(22,21,0),(21,20,0),(20,19,1),(19,18,0),(18,17,0),(17,2,0),(2,3,0),(13,12,1),(12,11,0),(11,10,0),(10,9,0),(9,8,0),(8,7,0),(7,6,0),(6,5,0),(5,4,0),(4,8,0),(4,16,1),(3,3,0),(3,16,1),(16,0,0),(0,15,0),(15,14,0),(14,3,0)], i=13, final_states=[0,15,14,3,16]))
a_t3.plot()
  
|
#check that Q_{1000L_h} = Q_{L_1}
eqQ(AutWord([1,0,0,0]).concat(h), a_t1)
True True |
#check that Q_{L_2} is a finite union of Hokkaido tiles
a2 = MakeAut([[0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],[1,0,0,0,0,0,1,1,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0]]).emonde().minimise()
a2.plot()
eqQ(a2.concat(h), a_t2)
True True 
|
#check that Q_{L_3} is a finite union of Hokkaido tiles
a3 = MakeAut([[0,0,0,0,0,1,0,0,0,0],[1,0,0,0,0,0,1,1,0,0,0,0,0]]).emonde().minimise()
a3.plot()
eqQ(a3.concat(h), a_t3)
True True 
|
########################################################
# Construction of the languages B1, B2, B3, C1, C2, C3 #
########################################################
|
|
c1 = FastAutomaton([(1, 9, 0), (2, 0, 0), (3, 2, 0), (4, 3, 0), (5, 4, 0), (6, 1, 0), (6, 5, 1), (7, 6, 0), (8, 7, 0), (9, 8, 0)], i=6, final_states=[0])
c1.plot()
c2 = FastAutomaton([(1, 24, 0), (2, 0, 0), (3, 2, 0), (4, 3, 0), (5, 4, 0),(6, 5, 0), (7, 15, 0), (7, 5, 1), (8, 16, 0), (9, 17, 0), (9, 1, 1),(10, 5, 1), (11, 18, 0), (12, 11, 0), (13, 12, 0), (13, 1, 1), (14, 10,0), (15, 14, 0), (16, 9, 0), (16, 5, 1), (17, 7, 0), (18, 8, 0), (18, 1,1), (19, 6, 1), (20, 19, 1), (21, 20, 0), (22, 21, 0), (23, 22, 0), (24,23, 0)], i=13, final_states=[0])
c2.plot()
c3 = FastAutomaton([(1, 18, 0), (2, 0, 0), (3, 2, 0), (4, 3, 0), (5, 4, 0),(6, 5, 0), (7, 5, 1), (8, 7, 0), (9, 8, 0), (10, 9, 0), (11, 10, 0),(12, 11, 0), (12, 1, 1), (13, 6, 1), (14, 13, 1), (15, 14, 0), (16, 15,0), (17, 16, 0), (18, 17, 0)], i=12, final_states=[0])
c3.plot()
  
|
a3.equals_langages(c3)
True True |
#check that Q_{L_i} = Q_{C_i.L_h}
print eqQ(a_t1, c1.concat(h))
print eqQ(a_t2, c2.concat(h))
print eqQ(a_t3, c3.concat(h))
True True True True True True |
#compute F_i = {q in states of a}{Q_{C_i} is a subset of Q_{L_q}}
if False:
F1 = []
F2 = []
F3 = []
i = A.initial_state()
for e in A.states():
A.set_initial_state(e)
if Proj(A, c1).equals_langages(Z(c1)):
F1.append(e)
if Proj(A, c2).equals_langages(Z(c2)):
F2.append(e)
if Proj(A, c3).equals_langages(Z(c3)):
F3.append(e)
A.set_initial_state(i)
else:
F1=[6]
F2=[16]
F3=[12, 16, 36, 55]
print "F1=%s, F2=%s, F3=%s"%(F1, F2, F3)
F1=[6], F2=[16], F3=[12, 16, 36, 55] F1=[6], F2=[16], F3=[12, 16, 36, 55] |
#compute languages D_i from F_i
d1 = A.copy()
d1.set_final_states(F1)
d1 = d1.emonde().minimise()
print d1
d2 = A.copy()
d2.set_final_states(F2)
d2 = d2.emonde().minimise()
print d2
d3 = A.copy()
d3.set_final_states(F3)
d3 = d3.emonde().minimise()
print d3
FastAutomaton with 192 states and an alphabet of 2 letters FastAutomaton with 191 states and an alphabet of 2 letters FastAutomaton with 191 states and an alphabet of 2 letters FastAutomaton with 192 states and an alphabet of 2 letters FastAutomaton with 191 states and an alphabet of 2 letters FastAutomaton with 191 states and an alphabet of 2 letters |
#compute languages E_i
Ah = A.concat(h)
e2 = Proj(d2.concat(c2).concat(h), Ah)
e3 = Proj(d3.concat(c3).concat(h), Ah).intersection(e2.complementary())
e1 = Proj(d1.concat(c1).concat(h), Ah).intersection((e2.union(e3)).complementary())
e2 = e2.emonde()
e3 = e3.emonde()
print e1
print e2
print e3
FastAutomaton with 205 states and an alphabet of 2 letters FastAutomaton with 205 states and an alphabet of 2 letters FastAutomaton with 205 states and an alphabet of 2 letters FastAutomaton with 205 states and an alphabet of 2 letters FastAutomaton with 205 states and an alphabet of 2 letters FastAutomaton with 205 states and an alphabet of 2 letters |
#plot E_1
m.plot2(tss=e1)
.png)
|
#plot E_2
m.plot2(tss=e2)
.png)
|
#plot E3
m.plot2(tss=e3)
.png)
|
#check that Z(A L_h) = E1 u E2 u E3
print e1.union(e2).union(e3).equals_langages(Z(A.concat(h)))
True True |
#plot the whole fractal with color corresponding to E1, E2 and E3
m.plot3(la=[M.union(e1.union(e2).union(e3)), e1, e2, e3])
.png)
|
#compute A_1 such that Z(E_1) = Z(A_1 L_h)
e1 = e1.emonde()
A1 = e1.copy()
for c in e1.strongly_connected_components():
if len(c) == 5:
#check that every state of this component is final
if len([e for e in c if e1.is_final(e)]) == 5:
#look for the only state from which two transition are leaving
l = [e for e in c if e1.succ(e, 0)!= -1 and e1.succ(e, 1)!= -1]
if len(l) == 1:
e = l[0]
A1.set_succ(e, 0, -1) #remove these transitions
A1.set_succ(e, 1, -1)
A1.set_final_states([e]) #set this state as the only final state
A1 = A1.emonde().minimise()
print A1
#check that A_1 is correct
Z(e1).equals_langages(Z(A1.concat(h)))
FastAutomaton with 205 states and an alphabet of 2 letters True FastAutomaton with 205 states and an alphabet of 2 letters True |
#compute A_2 such that Z(E_2) = Z(A_2 L_h)
e2 = e2.emonde()
A2 = e2.copy()
for c in e2.strongly_connected_components():
if len(c) == 5:
#check that every state of this component is final
if len([e for e in c if e2.is_final(e)]) == 5:
#look for the only state having a loop
l = [e for e in c if e2.succ(e, 0) == e]
if len(l) == 1:
e = l[0]
A2.set_succ(e, 0, -1) #remove these transitions
A2.set_succ(e, 1, -1)
A2.set_final_states([e]) #set this state as the only final state
print A2
#check that A_2 is correct
Z(e2).equals_langages(Z(A2.concat(h)))
FastAutomaton with 205 states and an alphabet of 2 letters True FastAutomaton with 205 states and an alphabet of 2 letters True |
#compute A_3 such that Z(E_3) = Z(A_3 L_h)
e3 = e3.emonde()
A3 = e3.copy()
for c in e3.strongly_connected_components():
if len(c) == 5:
#check that every state of this component is final
if len([e for e in c if e3.is_final(e)]) == 5:
#look for the only state having a loop
l = [e for e in c if e3.succ(e, 0) == e]
if len(l) == 1:
e = l[0]
A3.set_succ(e, 0, -1) #remove these transitions
A3.set_succ(e, 1, -1)
A3.set_final_states([e]) #set this state as the only final state
print A3
#check that A_3 is correct
Z(e3).equals_langages(Z(A3.concat(h)))
FastAutomaton with 205 states and an alphabet of 2 letters True FastAutomaton with 205 states and an alphabet of 2 letters True |
#compute B_1
B1 = A1.copy()
if False:
F1 = []
i = B1.initial_state()
for e in B1.states():
B1.set_initial_state(e)
if Proj(B1.concat(h), a_t1).equals_langages(Z(a_t1)) and not A1.is_final(e):
F1.append(e)
B1.set_initial_state(i)
else:
F1 = [6]
print F1, A1.final_states()
B1.set_final_states(F1)
B1 = B1.emonde().minimise()
print B1
#check that Q_{B_1.C_1.L_h} = Q_{A_1.L_h}
print eqQ(B1.concat(c1).concat(h), A1.concat(h))
print eqQ(e1, A1.concat(h))
print eqQ(B1.concat(c1).concat(h), e1)
[6] [0] FastAutomaton with 200 states and an alphabet of 2 letters True True True [6] [0] FastAutomaton with 200 states and an alphabet of 2 letters True True True |
#compute B_2
if False:
F2 = []
i = A2.initial_state()
for e in A2.states():
A2.set_initial_state(e)
if Proj(A2.concat(h), a_t2).equals_langages(Z(a_t2)) and not A2.is_final(e):
#if Proj(B2, a2).equals_langages(Z(a2)):
F2.append(e)
A2.set_initial_state(i)
else:
F2 = [12]
print F2
B2 = A2.copy()
B2.set_final_states(F2)
B2 = B2.emonde().minimise()
print B2
#check that Q_{B_2.C_2.L_h} = Q_{A_2.L_h}
eqQ(B2.concat(c2).concat(h), A2.concat(h))
[12] FastAutomaton with 191 states and an alphabet of 2 letters True [12] FastAutomaton with 191 states and an alphabet of 2 letters True |
#compute B_3
B3 = A3.copy()
if False:
F3 = []
i = B3.initial_state()
for e in B3.states():
B3.set_initial_state(e)
#if Proj(B3.concat(h), a_t3).equals_langages(Z(a_t3)) and not B3.is_final(e):
if Proj(B3, a3).equals_langages(Z(a3)): # and not B3.is_final(e):
F3.append(e)
B3.set_initial_state(i)
else:
F3 = [12]
print F3
B3.set_final_states(F3)
B3 = B3.emonde().minimise()
print B3
#check that Q_{B_3.C_3.L_h} = Q_{A_3.L_h}
eqQ(B3.concat(c3).concat(h), A3.concat(h))
[12] FastAutomaton with 191 states and an alphabet of 2 letters True [12] FastAutomaton with 191 states and an alphabet of 2 letters True |
################################################################
# Verification that B1, B2, B3, C1, C2, C3 satisfy the theorem #
################################################################
|
|
#check that the union of these parts is the whole fractal
ah1 = B1.concat(c1).concat(h)
ah2 = B2.concat(c2).concat(h)
ah3 = B3.concat(c3).concat(h)
ah = Z(ah1.union(ah2).union(ah3))
print eqQ(A.concat(h), ah)
print eqQ(s.unshift(0,3), M.union(ah))
True True True True |
m.plot3(la=[M.union(ah), ah1, ah2, ah3], colormap='CMRmap')
.png)
|
#automaton recognizing the diagonal
diag = FastAutomaton([(0,0,(i,i)) for i in m.C]+[(0,1,(i,j)) for i in m.C for j in m.C if i != j]+[(1,1,(i,j)) for i in m.C for j in m.C],i=0, final_states=[0]).emonde()
diag.plot()
|
#check that adherences of tiles of type 1 doesn't intersect
ch = c1.concat(h)
H = B1.concat(Pref(ch))
D = diag.intersection(B1.product(B1)).concat(Pref(ch.product(ch).emonde().minimise()))
P = H.product(H).emonde().minimise()
r = arelinf.intersection(P.intersection(D.complementary()))
r = S(r)
r.is_empty()
4 [] True 4 [] True |
#check that adherences of tiles of type 2 doesn't intersect
ch = c2.concat(h)
H = B2.concat(ch) #Pref(ch))
D = diag.intersection(B2.product(B2).emonde().minimise()).concat(ch.product(ch).emonde().minimise())
P = H.product(H).emonde().minimise()
r = arelinf.intersection(P.intersection(D.complementary()))
r = S(r)
r.is_empty()
0 [] True 0 [] True |
#check that adherences of tiles of type 3 doesn't intersect
#ch = Pref(c3.concat(h))
ch = c3.concat(h)
H = B3.concat(ch)
D = diag.intersection(B3.product(B3).emonde().minimise()).concat(ch.product(ch).emonde().minimise())
P = H.product(H)
r = arelinf.intersection(P.intersection(D.complementary()))
r = S(r)
r.is_empty()
0 [] True 0 [] True |
#define phi
A = B1.concat(c1).union(B2.concat(c2).union(B3.concat(c3)))
Ah = A.concat(h)
def phi(L):
ai = S(Z(L).product(Z(Ah)).emonde().minimise().intersection(arelinf))
return ah.intersection(ai.proji(1).concat(FastAutomaton(m.default_ss())))
|
|
#check that phi(B_1 Pref(Z(C_1 L_h))) = B_1 C_1 L_h
Z(phi(B1.concat(Pref(Z(c1.concat(h)))))).equals_langages(Z(B1.concat(c1).concat(h)))
10 [303, 305, 306, 307, 308, 282, 284, 285, 286, 287, 18, 20, 21, 22, 23, 24, 25, 27, 28, 43, 44, 45, 46, 47, 49, 50, 33, 34, 35, 36, 37] True 10 [303, 305, 306, 307, 308, 282, 284, 285, 286, 287, 18, 20, 21, 22, 23, 24, 25, 27, 28, 43, 44, 45, 46, 47, 49, 50, 33, 34, 35, 36, 37] True |
#check that phi(B_2 Pref(Z(C_2 L_h))) = B_2 C_2 L_h
Z(phi(B2.concat(Pref(Z(c2.concat(h)))))).equals_langages(Z(B2.concat(c2).concat(h)))
19 [667, 669, 670, 671, 672, 737, 746, 749, 945, 947, 745, 747, 944, 946, 948, 270, 272, 273, 274, 275, 276, 277, 279, 280, 297, 298, 299, 300, 301, 303, 304, 360, 361, 362, 364, 365, 261, 262, 263, 264, 265] False 19 [667, 669, 670, 671, 672, 737, 746, 749, 945, 947, 745, 747, 944, 946, 948, 270, 272, 273, 274, 275, 276, 277, 279, 280, 297, 298, 299, 300, 301, 303, 304, 360, 361, 362, 364, 365, 261, 262, 263, 264, 265] False |
#check that phi(B_3 Pref(Z(C_3 L_h))) = B_3 C_3 L_h
Z(phi(B3.concat(Pref(Z(c3.concat(h)))))).equals_langages(Z(B3.concat(c3).concat(h)))
18 [449, 451, 452, 453, 454, 425, 428, 438, 440, 442, 254, 256, 257, 258, 259, 260, 261, 263, 264, 284, 285, 286, 287, 288, 290, 291, 658, 669, 670, 672, 673, 278, 279, 280, 281, 282] True 18 [449, 451, 452, 453, 454, 425, 428, 438, 440, 442, 254, 256, 257, 258, 259, 260, 261, 263, 264, 284, 285, 286, 287, 288, 290, 291, 658, 669, 670, 672, 673, 278, 279, 280, 281, 282] True |
#check that phi(B_2 C_2 Pref(Z(L_h))) = B_2 C_2 L_h
t1 = phi(B2.concat(c2).concat(h))
t2 = B2.concat(c2).concat(h)
print Z(t1).equals_langages(Z(t2))
t2.included(Z(t1))
13 [467, 469, 470, 471, 472, 447, 449, 450, 451, 452, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 35, 256, 258, 259, 248, 249, 250, 251, 252] True True 13 [467, 469, 470, 471, 472, 447, 449, 450, 451, 452, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 34, 35, 256, 258, 259, 248, 249, 250, 251, 252] True True |
#zoom on the Rauzy fractal
m.draw_zoom(tss=A.concat(h))
Jul 11 17:52:05 python[624] <Warning>: void CGSUpdateManager::log() const: conn 0x15bd3: spurious update. Jul 11 17:52:05 python[624] <Warning>: void CGSUpdateManager::log() const: conn 0x15bd3: spurious update. |
#draw the zoom on the Rauzy fractal, with tiles of type 1 in black, tiles of type 2 in purple, tiles of type 3 in yellow-orange, and the part of dimension < 2 in gray
m.plot3(la=[M.union(ah), ah1, ah2, ah3], colormap='CMRmap', ajust=False)
.png)
|
|
|